package com.hxgis.common.utils.quickhull;



import com.hxgis.common.utils.quickhull.datastructures.LinkedList;
import com.hxgis.common.utils.quickhull.datastructures.LinkedListNode;

import java.awt.geom.Point2D;

/**
 * @Author: wrh
 * @Date: 2019/7/2 11:35
 * @Version 1.0
 */
public class QuickHull implements Algorithm {

    @Override
    public LinkedList useAlgorithm(LinkedList points) {

        if (points.getLength() < 4) {
            return points;
        }
        Point2D.Double minX = findMin(points.getHead());
        Point2D.Double maxX = findMax(points.getHead());

        LinkedList positive = new LinkedList();
        LinkedList negative = new LinkedList();

        pruneInapplicablePoints(minX, minX, maxX, points.getHead(), positive, negative);
        return mergeResults(iterate(positive), iterate(negative));

    }

    private Point2D.Double findMax(LinkedListNode head) {
        Point2D.Double max = null;
        for (LinkedListNode current = head; current != null; current = current.getNext()) {
            if (max == null || max.getX() < current.getPoint().getX()) {
                max = current.getPoint();
            }
        }
        return max;
    }

    private Point2D.Double findMin(LinkedListNode head) {
        Point2D.Double min = null;
        for (LinkedListNode current = head; current != null; current = current.getNext()) {
            if (min == null || min.getX() > current.getPoint().getX()) {
                min = current.getPoint();
            }

        }
        return min;

    }

    private Double checkRotation(Point2D.Double A, Point2D.Double B, Point2D.Double P) {

        return (A.getX() * (B.getY() - P.getY()) + B.getX() * (P.getY() - A.getY()) + P.getX() * (A.getY() - B.getY()));

    }

    private LinkedList iterate(LinkedList points) {

        if (points.getLength() < 4) {
            return trivialHull(points);
        }
        Point2D.Double A = points.getHead().getPoint();
        Point2D.Double B = points.getHead().getNext().getPoint();
        LinkedList negative = new LinkedList();
        LinkedList positive = new LinkedList();

        Point2D.Double P = findPivotPoint(A, B, points.getHead());

        if (P == null) {
            positive.insert(A);
            positive.insert(B);
            return positive;
        }
        pruneInapplicablePoints(A, B, P, points.getHead(), positive, negative);

        LinkedList res1 = iterate(positive);
        LinkedList res2 = iterate(negative);
        return mergeResults(res1, res2);

    }

    private LinkedList mergeResults(LinkedList res1, LinkedList res2) {
        LinkedList result = new LinkedList();
        LinkedListNode current = null;
        if (res1 != null) {
            current = res1.getHead();

            while (current != null) {
                result.insert(current.getPoint());
                current = current.getNext();
            }
        }
        if (res2 != null) {
            current = res2.getHead();
            while (current != null) {
                result.insert(current.getPoint());
                current = current.getNext();
            }
        }
        return result;
    }

    private LinkedList trivialHull(LinkedList points) {
        LinkedList res = new LinkedList();
        if (points.getLength() < 2) {
            return res;
        } else if (points.getLength() == 2) {
            res.insert(points.getHead().getNext().getPoint());
            return res;
        } else {
            res.insert(points.getHead().getNext().getNext().getPoint());
            res.insert(points.getHead().getNext().getPoint());
            return res;
        }
    }

    private Point2D.Double findPivotPoint(Point2D.Double A, Point2D.Double B, LinkedListNode head) {
        Point2D.Double tempPoint, P;
        double dist;
        double maxDist = 0;
        P = null;
        for (LinkedListNode current = head; current != null; current = current.getNext()) {
            tempPoint = current.getPoint();
            dist = Math.abs((tempPoint.getX() - A.getX()) * (B.getY() - A.getY()) - (tempPoint.getY() - A.getY()) * (B.getX() - A.getX()));
            if (maxDist < dist) {
                maxDist = dist;
                P = tempPoint;
            }
        }
        return P;
    }

    private void pruneInapplicablePoints(Point2D.Double A, Point2D.Double B, Point2D.Double P, LinkedListNode head, LinkedList positive, LinkedList negative) {
        positive.insert(A);
        positive.insert(P);
        negative.insert(P);
        negative.insert(B);
        for (LinkedListNode current = head; current != null; current = current.getNext()) {
            if (checkRotation(A, P, current.getPoint()) > 0) {
                positive.insert(current.getPoint());
            }
            if (checkRotation(P, B, current.getPoint()) > 0) {
                negative.insert(current.getPoint());
            }
        }
    }
}
